Asymmetric Encryption

Reminder: In asymmetric encryption schemes, the parties use different keys, that are mathematically related to each other.

Exercise

Why asymmetric encryption is useful?
Give a few examples where it can be used?

RSA

RSA is an asymmetric encryption algorithm by Ron Rivest, Adi Shamir, and Leonard Adleman. It was published in 1977. Its security is based on the hardness of factorization problem. However, now it has its own problem, called the RSA problem. RSA is slow, and is not used for encrypting large data, but it's mostly used to encrypt the symmetric key that is used for encryption.

p, q, two big prime numbers (private, chosen)
n = pq, φ(n) = (p-1)(q-1) (public, calculated)
e, with gcd(φ(n), e) = 1, 1 < e < φ(n) (public, chosen)
d = e - 1 mod φ(n) (private, calculated)
$E(M) = M^e \mod n$
$D(M) = M^d \mod n$
$D(E(M)) = M^{ed} \mod n = M$

Exercise

How to test if a number is prime?

RSA EXAMPLE

p = 5; q = 11 => n = 55
φ(n) = 40
e = 3 => d = 27
- Because ed = 1 mod φ(n)
Public key: (e, n)
Private key: (d, n)
Encryption
- M = 2
Encryption(M) = $ M^e\mod n$ = $2^3\mod n$ = 8
Decryption(8) = $ M^d\mod n$ = $8^{27} \mod n$ = 2



In [ ]:

    
2 ** 3 % 55



In [ ]:

    
8 ** 27



In [ ]:

    
8 ** 27 % 55

Exercise

Why can't we just use asymmetric encryption?

OpenSSL

To generate keys, use the following instructions:

openssl genrsa -out private_key.pem 2048
 openssl pkcs8 -topk8 -inform PEM -outform DER -in private_key.pem -out private_key.der -nocrypt
 openssl rsa -in private_key.pem -pubout -outform DER -out public_key.der



In [ ]:

    
%%bash
openssl genrsa -out private_key.pem 2048
openssl pkcs8 -topk8 -inform PEM -outform DER -in private_key.pem -out private_key.der -nocrypt
openssl rsa -in private_key.pem -pubout -outform DER -out public_key.der



In [ ]:

    
# import key from a file. E.g., previously generated by OpenSSL
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization

with open("private_key.pem", "rb") as key_file:
     private_key = serialization.load_pem_private_key(
            key_file.read(),
            password=None,
            backend=default_backend())
public_key = private_key.public_key()



In [ ]:

    
# Generate a 2048 bit private key
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import rsa

private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
    backend=default_backend())
# to get the public key
public_key = private_key.public_key()



In [ ]:

    
2 ** 16 +1



In [ ]:

    
print(bin(2**16 + 1))
print(bin(2**1 + 1))

Exercise

What's wrong with textbook RSA?

It's all about padding

Textbook RSA is not IND-CPA secure, therefore we use Optimal Asymmetric Encryption Padding (OAEP). There are also other attacks against RSA with improper padding

image souce: wikipedia



In [ ]:

    
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding

message = b"The SECRET KEY"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA1()),
        algorithm=hashes.SHA1(),
        label=None))



In [ ]:

    
print(ciphertext)



In [ ]:

    
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding

plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA1()),
        algorithm=hashes.SHA1(),
        label=None))



In [ ]:

    
print(plaintext)